package com.codingvip.tree;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
import java.util.Vector;

/**
 * @author hansongtao
 */
public class NodePath {
    public static void main(String[] args) {
//         [3,5,1,6,2,0,8,null,null,7,4]
        TreeNode treeNode33 = new TreeNode(3);
        TreeNode treeNode55 = new TreeNode(5);
        TreeNode treeNode11 = new TreeNode(1);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode22 = new TreeNode(2);
        TreeNode treeNode5 = new TreeNode(8);
        TreeNode treeNode77 = new TreeNode(7);
        TreeNode treeNode44 = new TreeNode(4);
        TreeNode treeNode00 = new TreeNode(0);

        treeNode33.left = treeNode55;
        treeNode33.right = treeNode11;

        treeNode55.left = treeNode6;
        treeNode55.right = treeNode22;


        treeNode11.left = treeNode00;
        treeNode11.right = treeNode5;

        treeNode22.left = treeNode77;
        treeNode22.right = treeNode44;

        NodePath nodePath = new NodePath();
        TreeNode treeNode555 = new TreeNode(5);
        TreeNode treeNode444 = new TreeNode(4);
        System.out.println(nodePath.lowestCommonAncestor(treeNode33, treeNode555, treeNode444));
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==p || root==q) {
            return root;
        }

        TreeNode leftNode=lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode=lowestCommonAncestor(root.right,p,q);

        if(leftNode==null) {
            return rightNode;
        }
        if(rightNode==null) {
            return leftNode;
        }

        return root;
    }


//    public void getPath(TreeNode root, TreeNode end, Vector<TreeNode> path) {
//        Stack stk = new Stack();
//        TreeNode p = root, pre = null;
//        while (p != null || !stk.isEmpty()) {
//            while (p != null) {
//                stk.push(p);
//                path.add(p);
//                if (p.val == end.val) {
//                    return;
//                }
//                p = p.left;
//            }
//            p = (TreeNode) stk.pop();
//            if (p.right != null ) {
//                //|| p.right == pre
//                path.remove(path.lastElement());
//                stk.pop();
//                pre = p;
//                p = null;
//
//            } else {
//                p = p.right;
//            }
//
//        }
//    }
//
//    TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        Vector<TreeNode> path1 = new Vector<>(), path2 = new Vector<>();
//        getPath(root, p, path1);
//        getPath(root, q, path2);
//        int n = Math.min(path1.size(), path2.size());
//        TreeNode last = null;
//
//        for (int i = 0; i < n; i++) {
//            if (path1.get(i) != path2.get(i)) {
//                return last;
//            }
//            last = path1.get(i);
//        }
//        return last;
//    }


}
